package com.jz;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * Description: JZ49 丑数
 *
 * @author weiruibai.vendor
 * Date: 2022/9/13 17:22
 */
public class JZ49 {

    public static void main(String[] args) {
        System.out.println(GetUglyNumber_Solution(7));
    }

    public static int GetUglyNumber_Solution(int n) {
        if (n < 1) {
            return 0;
        }
        List<Integer> factory = new ArrayList<Integer>() {{
            add(2);
            add(3);
            add(5);
        }};
        Set<Long> set = new HashSet<>();
        PriorityQueue<Long> queue = new PriorityQueue<>();
        queue.add(1l);
        set.add(1l);
        int ans = 1;
        for (int i = 1; i <= n; i++) {
            long poll = queue.poll();
            ans = (int) poll;
            for (int j = 0; j < factory.size(); j++) {
                Long res = poll * factory.get(j);
                if (set.add(res)) {
                    queue.add(res);
                }
            }
        }
        return ans;
    }
}
